"""
题目背景：

    在学术研究中，学者之间的合作关系可以构成一个复杂的网络。分析这个网络，例如找出两位学者之间的最短合作路径（即“学术圈的六度分隔理论”），是一个有趣且有意义的问题。

题目描述：

    请你设计一个 CollaborationNetwork 类来模拟学者合作网络。该网络由一系列论文和它们的作者构成。你需要实现一个方法，用于查找任意两位学者之间的最短合作路径长度。
    路径长度定义为从一个学者到另一个学者需要经过的合作关系数量。例如，A和B合写过论文，他们的路径长度是1。A和B没合作过，但B和C合作过，则A到C的路径长度是2。

需要：
    1. 实现 CollaborationNetwork 类，包含以下方法：
        –__init__(self): 初始化一个空的合作网络。
        –add_paper(self, authors: List[str]): 添加一篇论文及其作者列表。网络中的节点是学者，同一篇论文的作者之间都存在一条边。
        –get_shortest_path(self, author1: str, author2: str) -> int: 计算并返回两位学者之间的最短合作路径长度。如果两人不连通，返回-1。如果查询的学者是同一个人，返回0。

测试用例：

输入 (author1, author2)	        预期输出

("A", "B")	                 1
("A", "C")	               1
("B", "D")	                   1
("A", "D")	                2
("C", "D")                   	2
("A", "E")	                 3
("B", "E")                  	2
("F", "G")	                    1
("A", "F")	                   -1
("E", "G")	                   -1
("A", "A")	                 0
("D", "C")	                  2
("H", "A")	                -1

"""


class CollaborationNetwork:
    def __init__(self):
        """
        初始化合作网络
        用字典存储邻接表：键为学者姓名，值为该学者的直接合作者列表
        """
        self.network = {}

    # 添加一篇论文及其作者列表为一张图。网络中的节点是学者，同一篇论文的作者之间都存在一条边。
    def add_paper(self, authors):
        """
        添加一篇论文，建立作者间的合作关系
        同一论文的所有作者两两之间互设为直接合作者
        Args:
            authors: 论文作者列表（list of str）
        """
        if len(authors) < 2:
            return
        # 遍历所有作者对，建立双向合作关系
        n = len(authors)
        for i in range(n):
            author_a = authors[i]
            # 若作者a不在网络中，初始化其合作者列表
            if author_a not in self.network:
                self.network[author_a] = []
            for j in range(i + 1, n):
                author_b = authors[j]
                # 若作者b不在网络中，初始化其合作者列表
                if author_b not in self.network:
                    self.network[author_b] = []
                # 避免重复添加同一合作关系
                if author_b not in self.network[author_a]:
                    self.network[author_a].append(author_b)
                if author_a not in self.network[author_b]:
                    self.network[author_b].append(author_a)

    def get_shortest_path(self, author1, author2):
        """
        计算两位学者的最短合作路径长度
        Returns:
            路径长度（-1表示不连通，0表示同一人）
        """
        # 同一学者直接返回0
        if author1 == author2:
            return 0
        # 任意学者不在网络中，返回-1
        if author1 not in self.network  or  author2 not in self.network:
            return -1
        # BFS所需的队列（用列表模拟，通过pop(0)实现出队）
        queue = []
        # 记录已访问的学者（避免循环访问）
        visited = []
        # 初始节点入队：(当前学者, 距离) 注意：queue里面的每一个元素都是元组！
        # 存储待处理的节点及距离：队列中的每个元素是一个元组 (当前学者, 距离)，其中 距离 表示从起始学者到 “当前学者” 的最短路径长度。
        # 保证 “广度优先”：队列遵循 “先进先出（FIFO）” 原则，先入队的节点（距离近的）会被优先处理。例如，先处理距离为 1 的所有直接合作者，再处理距离为 2 的间接合作者，以此类推。
        # 终止条件：当队列空了，说明所有可达节点都已处理完，若仍未找到目标学者，则两人不连通。
        queue.append((author1, 0))

        #visited 用于记录已经处理过的节点，避免重复访问和循环遍历，确保算法高效且正确。具体来说：
        # 防止重复处理：同一学者可能通过不同路径被多次访问（例如 A 合作 B，B 合作 C，A也可能通过其他路径间接访问C），visited 会标记已处理的学者，避免其被反复加入队列。
        # 避免循环：若存在环形合作关系（例如 A 合作 B，B 合作 C，C 合作 A），visited 会阻止算法在环中无限循环（如 A→B→C→A→B...）。
        visited.append(author1)
        while queue:
            # 弹出队（队列头部元素）
            current_author, distance = queue.pop(0)
            # 遍历当前学者的所有直接合作者
            for neighbor in self.network[current_author]:
                if neighbor == author2:
                    # 找到目标，返回当前距离+1（直接合作）
                    return distance + 1
                if neighbor not in visited:
                    # 未访问过的节点加入队列
                    visited.append(neighbor)
                    #下面这行代码体现：已经visit的节点 不会再被加入queue队列，进而不会再从queue队列中被取出、判断，避免循环
                    queue.append((neighbor, distance + 1))
        # 遍历完所有可达节点仍未找到目标，返回-1
        return -1


if __name__ == "__main__":
    # 初始化网络
    cn = CollaborationNetwork()
    # 添加论文构建合作关系 注意 两两之间都是会有链接的
    cn.add_paper(["A", "B", "C"])  # A-B、A-C、B-C
    cn.add_paper(["B", "D"])  # B-D
    cn.add_paper(["D", "E"])  # D-E
    cn.add_paper(["F", "G"])  # F-G
    print("构建好的图是:",cn.network)  #构建好的图是: {'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B'], 'D': ['B', 'E'], 'E': ['D'], 'F': ['G'], 'G': ['F']}
    # 测试用例
    test_cases = [
        ("A", "B"),  # 1
        ("A", "C"),  # 1
        ("B", "D"),  # 1
        ("A", "D"),  # 2 (Alice->B->D)
        ("C", "D"),  # 2 (C->B->D)
        ("A", "E"),  # 3 (Alice->B->D->E)
        ("B", "E"),  # 2 (B->D->E)
        ("F", "G"),  # 1
        ("A", "F"),  # -1 (不连通)
        ("E", "G"),  # -1 (不连通)
        ("A", "A"),  # 0
        ("D", "C"),  # 2 (D->B->C)
        ("H", "A"),  # -1 (H不在网络中)
    ]

    # 执行测试并输出结果
    for a1, a2 in test_cases:
        print(f"{a1}到{a2}的最短路径长度：{cn.get_shortest_path(a1, a2)}")